package leetcode_题库;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/9/20 9:11
 */
public class _455_分发饼干 {
    public static void main(String[] args) {
        int[] g = new int[]{1,2,7,10}; //胃口
        int[] s = new int[]{1,3,5,9}; //饼干
        System.err.println(findContentChildren(g, s));
    }

    /**
     * 贪心算法，先排序，再喂饱
     * > 2022/09/20 09:23:42
     * 解答成功:
     * 	执行耗时:7 ms,击败了100.00% 的Java用户
     * 	内存消耗:42.5 MB,击败了42.69% 的Java用户
     * @Author Ding
     * @Date 2022/9/20 9:23
     * @param g 胃口
     * @param s 饼干
     * @return int
     **/
    public static int findContentChildren(int[] g, int[] s) {
        //排序
        Arrays.sort(g);
        Arrays.sort(s);
        //计数器
        int cnt = 0;
        //饼干从最大开始
        int j = s.length - 1;
        //胃口从最大的开始
        for (int i = g.length - 1; i >= 0 ; i--) {
            //如果最大口径饼干能满足最大胃口的孩子，就计数器++，同时饼干--
            //无论满足与否，孩子都要--
            if (j >= 0 && s[j]>=g[i]){
                j--;
                cnt++;
            }
        }
        return cnt;
    }
}
